package codeRandomThoughts.Test332重新安排行程;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;


class Solution2 {
    private List<String> path = new LinkedList<>();
    private List<String> result = new ArrayList<>();
    boolean[] used;

    public List<String> findItinerary(List<List<String>> tickets) {
        //首先要对tickets数组排序
        tickets.sort((t1, t2) -> {
            if (t1.get(0).compareTo(t2.get(0)) == 0) {
                return t1.get(1).compareTo(t2.get(1));
            } else {
                return t1.get(0).compareTo(t2.get(0));
            }
        });
        used = new boolean[tickets.size() + 1];
        path.add("JFK");
        backtracking(tickets, "JFK");
        return result;
    }

    public void backtracking(List<List<String>> tickets, String startPos) {
        if (path.size() == tickets.size() + 1) {
            result = new ArrayList<>(path);
        }
        if (!result.isEmpty()) return;

        for (int i = 0; i < tickets.size(); i++) {
            List<String> ticket = tickets.get(i);
            if (!used[i] && ticket.get(0).equals(startPos)) {
                used[i] = true;
                String endPos = ticket.get(1);
                path.add(endPos);
                backtracking(tickets, endPos);
                used[i] = false;
                path.remove(path.size() - 1);
            }
        }
    }
}
